The use and application of computer graphics to an increasing number of systems environments continues to grow. This growth has been accelerated to an even greater extent with the availability of faster and faster information processing, storage, memory and retrieval devices. The speed of operation of such devices remains a high priority design objective. This is especially true in a graphics system and even to a greater extent with 3D graphics systems. Such graphics systems require a great deal of processing for huge amounts of data and the speed of data flow is critical in providing a new product or system or in designing graphics systems to apply to new uses.
In the field of computer graphics, many methods exist to draw polygons into a pixel grid. Polygons are used as drawing primitives for many applications such as Graphical User Interfaces, Computer Aided Design and 3D Computer Animation. Most techniques for drawing polygons reduce the polygon to a series of scan lines that align to the edges of the polygon and to the pixel grid. When these methods are implemented in hardware, the pixel grid is generally accessed in a sequential method, i.e. for each XY pixel access, the pixel grid is updated based on the XY address. For a pixel grid that has a large set-up time per pixel update, this can become a time bottleneck for the entire system.
In all data and information processing systems, and especially in computer graphics systems, much time is consumed in accessing data blocks from a memory or storage location, then processing that information and sending the processed information to another location for subsequent retention, access, processing and/or display. As the speed of new processors continues to increase, access time for accessing and retrieving data from memory is becoming more and more of a bottleneck in terms of system speed.
Graphic systems must be capable of performing more sophisticated functions in less time in order to process greater amounts of graphical data required by modern software applications. There is a continuing need for improvements in software methods and hardware implementations to draw three-dimensional objects using full color, shading, texture mapping and transparency blending. The development of raster display systems has dramatically reduced the overall cost and increased the capabilities of graphic systems. In a raster display system, a set of horizontal or orthogonal scan lines, each comprising a row of pixels, forms an array or grid of pixels to represent the entire screen area. The screen is preferably a cathode ray tube (CRT) or liquid crystal display (LCD) or the like capable of scanning the entire pixel grid at a relatively high rate to reduce flicker as much as possible.
The pixel data is preferably stored in a frame buffer comprising dynamic random access memories (DRAMs), where each pixel is represented by one or more bits depending upon the desired resolution, color, brightness and other variables. Typical display systems can draw screens with multiple colors with a variety of screen resolutions, such as, but not limited to, 640.times.480, 800.times.600, 1024.times.768, 1280.times.1024, or other combinations depending upon the software drivers and the hardware used. A video controller scans and converts the pixel data in the frame buffer to the control signals required by the screen system to display the information on the screen. The video controller scans each of the pixels sequentially, from top to bottom and from left to right, and converts pixel data into intensity values for corresponding pixels on the screen. In a color graphics system using a CRT, three separate beams are controlled i.e. one beam each for each of the primary colors, where the intensity of each of the beams is determined by the pixel value corresponding to the respective colors. A similar system is used for LCD devices. Each pixel value may comprise, for example, 24 bits, i.e. one 8-bit byte for each of the primary colors red, green and blue, where the byte value determines the intensity of the respective color to be displayed.
A pixel grid in memory is a representation of two dimensional space in a linear accessed memory. Linear accessed memory has incrementing addresses for each location in memory i.e. a one dimensional space. A two dimensional space can be represented in one dimensional addressing by creating a pitch value to the "Y" parameter, i.e. for each increment in "Y", a number of pixel grid locations exist in "X". This allows a linear address to be calculated from a two dimensional XY pixel grid access. Most methods for drawing to a pixel grid use the above method to access a pixel grid. The XY mapping is fixed at the time the polygons are being drawn based on the current two dimensional pixel grid in memory. From that point on, the pixel grid, unless noted otherwise, will be assumed to be a fixed two dimensional representation of a pixel grid in linear addressed memory.
A polygon is represented as a set of points in the pixel grid that map to the intersection of the polygon to be drawn. The definition of most lines and polygons are continuous functions that can only be approximated by the pixel grid. Polygons in computer graphics are generally drawn by decomposing the definition of the polygon to a set of boundary conditions called vertex points that represent approximations of the end points of the polygon into a pixel grid. Those vertex points are then decomposed to a set of scan lines for each Y scanning in the X direction for each pixel in the X direction contained within the polygon.
With specific reference to computer graphics applications, representations of images are stored in pixel-oriented frame buffers or display memory which may be implemented as Rambus-based DRAM (RDRAM). The frame of reference for the video buffers is a zero point relative to a matrix of storage positions for storing pixel values and information related to the pixel characteristics which define an image to be displayed. That zero point storage position corresponds to a zero point pixel position on a display screen utilized to display the image comprised of the stored pixels. A string or row of data from the buffer corresponds to a row of pixels on the display screen. As an image is refreshed on a display screen, each line of data stored in the video memory is sequentially accessed from memory and transferred to the display device to fill-in corresponding sequential lines of pixels on the display. Each such access and transfer has a delay time associated therewith which has heretofore been relatively unalterable because of the inherent dependence of the storing process on the scanning process, i.e. the initiation of each line of storage begins with the left-most pixel of each display scan line regardless of the position in the scan line which contains the first bit of image definition.
Also, in storing and retrieving information, delay is introduced when data has to be stored in and retrieved from system memory rather than the relatively faster RDRAM memory of the graphics subsystem. The graphics subsystem includes a relatively fast local memory or RDRAM which is faster than the system memory. Processing inefficiencies occur when information blocks cannot be accommodated by the fast local memory and have to be transferred to the system memory. Subsequently, when access to that information is needed, the fast graphics system must wait on the slower access from the system memory before processing and displaying any information that had to be stored on the system memory. Moreover, even when some system storage is unavoidable due to the data overhead of graphics applications, in the past there has not been any attempt to prioritize the data by types in order to optimize storage and retrieval times for the fast RDRAM and the relatively slower system memories.
Thus there is a need for an improved graphics information storage method and apparatus for storing texture map information by various information characteristics such that the storage destination is determined according to predetermined characteristics of the texture map data in order to minimize data storage and retrieval times.